/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2009 INRIA
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Authors: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
 */
#include "spin-barrier-impl.h"
#include "ns3/atomic.h"
#include <iostream>

namespace ns3 {

GlobalSpinBarrierImpl::GlobalSpinBarrierImpl (int n)
  : m_totalWaiters (n),
    m_waiters (0),
    m_release (0)
{}

GlobalSpinBarrierImpl::~GlobalSpinBarrierImpl ()
{}

void 
GlobalSpinBarrierImpl::Initialize (struct GlobalSpinBarrierContext *context)
{
  context->sense = 1;
}

void 
GlobalSpinBarrierImpl::Wait (struct GlobalSpinBarrierContext *context)
{
  context->sense = -context->sense;
  int waiters = AtomicExchangeAndAdd (&m_waiters, 1);
  if (waiters + 1 == m_totalWaiters)
    {
      AtomicExchangeAndAdd (&m_waiters, -m_totalWaiters);
      m_release = context->sense;
    }
  else
    {
      while (AtomicGet (&m_release) != context->sense)
        {
          // intel manual
          __asm__ ("pause");
        }
    }
}

struct TreeSpinBarrierNode
{
  int count;
  int parent;
  int k;
  int locksense __attribute__ ((aligned(128)));
};

TreeSpinBarrierImpl::TreeSpinBarrierImpl (int n)
  : m_totalWaiters (n),
    m_contextsInitialized (0)
{
  int fanIn = 4;
  m_nodes = new struct TreeSpinBarrierNode [n] ();
  int availIndex = 1;
  m_nodes[0].parent = -1;
  for (int i = 0; i < n; i++)
    {
      struct TreeSpinBarrierNode *node = &m_nodes[i];
      int left = n - availIndex;
      int nchildren = std::min (left, fanIn);
      node->count = nchildren + 1;
      node->k = nchildren + 1;
      node->locksense = 0;
      for (int j = 0; j < nchildren; j++)
        {
          m_nodes[availIndex + j].parent = i;
        }
      availIndex += nchildren;
    }
}

TreeSpinBarrierImpl::~TreeSpinBarrierImpl ()
{
  delete[] m_nodes;
}

void 
TreeSpinBarrierImpl::Initialize (struct TreeSpinBarrierContext *context)
{
  if (m_nodes[m_contextsInitialized].k == 1 &&
      m_nodes[m_contextsInitialized].parent != -1)
    {
      context->node = m_nodes[m_contextsInitialized].parent;
    }
  else
    {
      context->node = m_contextsInitialized;
    }
  context->sense = 0;
  m_contextsInitialized++;
}

void 
TreeSpinBarrierImpl::WaitAux (int sense, struct TreeSpinBarrierNode *node)
{
  int old = AtomicExchangeAndAdd (&node->count, -1);
  if (old == 1)
    {
      if (node->parent != -1)
        {
          WaitAux (sense, &m_nodes[node->parent]);
        }
      node->count = node->k;
      node->locksense = ! node->locksense;
    }
  while (AtomicGet (&node->locksense) != sense)
    {
      // intel manual
      __asm__ ("pause");
    }
}

void 
TreeSpinBarrierImpl::Wait (struct TreeSpinBarrierContext *context)
{
  struct TreeSpinBarrierNode *node = &m_nodes[context->node];
  context->sense = ! context->sense;
  WaitAux (context->sense, node);
}

} // namespace ns3 
